package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 581. 最短无序连续子数组
 * @date 2025/2/15 14:11
 */
public class E581 {

    /**
     * <h3>方法一：从左往右遍历一遍，从右往左遍历一遍</h3>
     *
     * @param nums 数组
     * @return 最短无序连续子数组的长度
     */
    public int findUnsortedSubarray1(int[] nums) {
        // 1. 准备maxFromLeft和minFromRight，分别表示从左往右遍历时遇到的最大值（排序后在从左往右最后），从右往左遍历时遇到的最小值（排序后在从右往左最后）
        int maxFromLeft = nums[0], minFromRight = nums[nums.length - 1];
        int start = 0, end = 0;
        // 2. 从左往右遍历一遍，找到最短无序连续子数组的结束位置
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < maxFromLeft) end = i;
            else if (nums[i] > maxFromLeft) maxFromLeft = nums[i];
        }
        // 3. 从右往左遍历一遍，找到最短无序连续子数组的起始位置
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] > minFromRight) start = i;
            else if (nums[i] < minFromRight) minFromRight = nums[i];
        }
        // 4. 返回最短无序连续子数组的长度。等于的时候都只有一个数字，排序不排序有什么区别
        return end > start ? end - start + 1 : 0;
    }
}
